/* 0. 代码随想录 */
typedef struct TreeNode TreeNode;

// step 1# 查找函数：在二叉搜索树中查找目标值
TreeNode* searchBST(TreeNode* root, int val) {
    // step 1.1# 如果当前节点为空 或者 找到目标值，直接返回该节点
    if (root == NULL || root->val == val) return root;

    // step 1.2# 定义一个结果指针
    TreeNode* result = NULL;

    // step 1.3# 如果目标值小于当前节点，往左子树查找
    if (val < root->val) result = searchBST(root->left, val);

    // step 1.4# 如果目标值大于当前节点，往右子树查找
    else if (val > root->val) result = searchBST(root->right, val);

    // step 1.5# 返回查找结果
    return result;
}

/* 1. 二叉搜索树搜索 */
/**
 * Definition for a binary tree node.
 * struct TreeNode {
 *     int val;
 *     struct TreeNode *left;
 *     struct TreeNode *right;
 * };
 */
/*
    1. 如果当前节点的 val 大于 tar，则搜索左子树
    2. 如果当前节点的 val 小于 tar，则搜索右子树
    3. 最后如果 NULL 或则 找到 tar，就结束递归
*/

typedef struct TreeNode TreeNode;

TreeNode *search(TreeNode *curNode, int val) {
    if (curNode == NULL || curNode->val == val) return curNode;

    if (curNode->val > val) return search(curNode->left, val);

    if (curNode->val < val) return search(curNode->right, val);

    // note # 这里要写上一个 return，不加上编译报错，虽然逻辑上不会执行
    return NULL;

}

struct TreeNode* searchBST(struct TreeNode* root, int val) {
    return search(root, val);
}